package backTrack;

import java.util.ArrayList;
import java.util.List;

public class generateParenthesis {
    List<String> list = new ArrayList<>();

    public List<String> generateParenthesis(int n) {
        backTrack(n, 0, 0, new StringBuffer());
        return list;
    }

    public void backTrack(int n, int left, int right, StringBuffer sb) {
        if (sb.length() == n * 2) {
            list.add(sb.toString());
            return;
        }
        if (left < n) {
            // 左or右
            sb.append('(');
            backTrack(n, left + 1, right, sb);
            sb.delete(sb.length() - 1, sb.length());
        }
        if (right < left) {
            sb.append(')');
            backTrack(n, left, right + 1, sb);
            sb.delete(sb.length() - 1, sb.length());
        }

    }

    public static void main(String[] args) {
        generateParenthesis obj = new generateParenthesis();
        List<String> lists = obj.generateParenthesis(2);

        for (String i : lists) {
            System.out.println(i);
        }
        System.out.println("============");

    }
}
